#include <cstdio>

struct Matrix
{
    int n, m, a[ 4 ][ 4 ];
};

void operator *= ( Matrix &a, const Matrix &b )
{
    Matrix c;
    int i, j, k;
    c.n = a.n; c.m = b.m;
    for ( i = 0; i < c.n; i++ )
        for ( j = 0; j < c.m; j++ )
            for ( c.a[ i ][ j ] = k = 0; k < a.m; k++ )
                c.a[ i ][ j ] = ( ( c.a[ i ][ j ] + a.a[ i ][ k ] * b.a[ k ][ j ] ) % 10007 + 10007 ) % 10007;
    a = c;
}

int main( )
{
    Matrix a, b, c;
    int n, p;
    int t, cas = 1;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d", &n);
        a.n = 1; a.m = 2;
        c.n = c.m = b.n = b.m = 2;
        b.a[ 0 ][ 0 ] = b.a[ 1 ][ 1 ] = 1;
        b.a[ 0 ][ 1 ] = b.a[ 1 ][ 0 ] = 0;
        c.a[ 0 ][ 0 ] = 4; c.a[ 0 ][ 1 ] = 0; c.a[ 1 ][ 0 ] = c.a[ 1 ][ 1 ] = 1;
        if ( n & 1 )
        {
            n = n / 2;
            a.a[ 0 ][ 0 ] = 2;
            a.a[ 0 ][ 1 ] = -5;
            p = 1;
            while ( p <= n ) p <<= 1;
            p >>= 1;
            while ( p )
            {
                b *= b;
                if ( p & n ) b *= c;
                p >>= 1;
            }
            a *= b;
            printf("Case #%d: %d\n", cas++, a.a[ 0 ][ 0 ]);
        }
        else
        {
            n = n / 2 - 1;
            a.a[ 0 ][ 0 ] = 2;
            a.a[ 0 ][ 1 ] = -4;
            p = 1;
            while ( p <= n ) p <<= 1;
            p >>= 1;
            while ( p )
            {
                b *= b;
                if ( p & n ) b *= c;
                p >>= 1;
            }
            a *= b;
            printf("Case #%d: %d\n", cas++, a.a[ 0 ][ 0 ]);
        }
    }
    return 0;
}
